iT邦幫忙

2023 iThome 鐵人賽

DAY 8
2
Web 3

淺談ZK Rollup系列 第 8

Day 08 - 零知識證明SP03:同態隱藏

  • 分享至 

  • xImage
  •  

又來到了特別篇章的單元了,再次提醒一下,一旦看到我的標題打的是SP,就代表著在接下來的篇章到來之前,有額外的東西需要做補充,一旦你了解副標題的名詞,便可以直接跳過,前往下一篇章。
好的,這個篇章要來講解同態隱藏(Homomorphic Hiding),在講同態隱藏之前,先來簡單說說同態。

同態(Homomorphism)

原本我打算用一個生活上遇到的事情來比喻同態這個東西,但後來思來想去,與其拿比喻來讓這一切複雜的東西變得更加混亂,不如直接拿數學式子來直接講解。
https://chart.googleapis.com/chart?cht=tx&chl=%24f(a)%2Bf(b)%3Df(a%2Bb)%24
當上面這個式子的成立,便可以說https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24這個函數擁有同態的特性,舉個例子,當今天https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%3D5x%24時,這個https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24便有同態的特性,證明如下:
https://chart.googleapis.com/chart?cht=tx&chl=%24f(a)%2Bf(b)%3D5a%2B5b%3D5(a%2Bb)%3Df(a%2Bb)%24
當然,這裡的運算可以不是加號,兩邊的運算符號也可以不用相等,像是符合https://chart.googleapis.com/chart?cht=tx&chl=%24f(a)*f(b)%3Df(a%2Bb)%24也符合同態,例如https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%3D2%5Ex%24,因為同底相乘等於指數相加,所以可得出以下證明:
https://chart.googleapis.com/chart?cht=tx&chl=%24f(a)f(b)%3D(2%5Ea)(2%5Eb)%3D2%5E%7B(a%2Bb)%7D%3Df(a%2Bb)%24
所以可以知道,擁有同態特性的函數https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24,帶入的參數在帶入前做特定操作跟帶入後做特定操作可以得出同樣結果。那這有什麼用呢?這可以幫助你在進行https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24運算時,可以把某些操作先做起來,使他可以比較好運算,基本上這就是擁有同態特性的好處,但如果擁有同態再加上隱藏的特性,那麼能做的事情,遠比你想得來的多。
https://cdn-icons-png.flaticon.com/512/4720/4720458.png

同態隱藏(Homomorphic Hiding)

剛剛講了同態,現在來說說隱藏吧!隱藏就如同字面上的意思,他把東西讓你找不到了,而這個東西呢,就是你帶入的參數https://chart.googleapis.com/chart?cht=tx&chl=%24x%24,所以擁有隱藏特性的https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24,可以讓你找不出https://chart.googleapis.com/chart?cht=tx&chl=%24x%24的影子,意思是你沒辦法用https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24去找回https://chart.googleapis.com/chart?cht=tx&chl=%24x%24原本的數值,所以同態隱藏便是具有同態還有隱藏,那能找到這種的函數嗎?有,肯定有,就舉個最愚蠢的例子,還記得剛剛說到https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%3D5x%24擁有同態特性吧,基本上只要是某數乘上https://chart.googleapis.com/chart?cht=tx&chl=%24x%24的函數都具有同態的特性,那麼我把某數https://chart.googleapis.com/chart?cht=tx&chl=%240%24會發生什麼事呢?可以發現神奇的事情發生了,當https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%3D0x%24時,他便符合同態隱藏了!
同態證明如下:

  • https://chart.googleapis.com/chart?cht=tx&chl=%24f(a)%2Bf(b)%3D0a%2B0b%3D0%24
  • https://chart.googleapis.com/chart?cht=tx&chl=%24f(a%2Bb)%3D0(a%2Bb)%3D0%24
  • https://chart.googleapis.com/chart?cht=tx&chl=%24f(a)%2Bf(b)%3Df(a%2Bb)%24
  • 所以此https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24具有加法同態

至於隱藏的特性,由於不論帶入什麼數字,出來的結果都是https://chart.googleapis.com/chart?cht=tx&chl=%240%24,你沒辦法透過這個https://chart.googleapis.com/chart?cht=tx&chl=%240%24來找出我當時帶入的https://chart.googleapis.com/chart?cht=tx&chl=%24x%24值為何,因此他便符合隱藏的特性,所以https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%3D0x%24便是一個穩穩妥妥的同態隱藏。那你肯定會問說這個函數具有什麼意義呢?雖然實作上並不會用到這個函數,但它提供了一個概念,什麼概念呢?便是如何生成一個具有同態隱藏的函數,讓我們來思考為什麼https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%3D0x%24會具有隱藏的效果?那是因為如果要從https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24推回去https://chart.googleapis.com/chart?cht=tx&chl=%24x%24,便需要將https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24除以https://chart.googleapis.com/chart?cht=tx&chl=%240%24,然而在自然數的規則中,並不存在除以https://chart.googleapis.com/chart?cht=tx&chl=%240%24的規則,因此他無法被還原,所以只要找出一個具有無法被還原的操作,以及一個擁有同態特性的函數,兩者結合,便能得出一個有同態隱藏特性的函數。至於要找出一個無法被還原的操作,可能會有點反直覺,但是繼續深究就背離我只想淺談的原則了,那一塊的內容便跟代數非常相關了,有興趣的人可以Google一下 「橢圓曲線」 ,對他進行更深入的研究,這裡便不繼續探討了!
那如果找到一個函數https://chart.googleapis.com/chart?cht=tx&chl=%24f(x)%24具有同態隱藏的特性,那有什麼用呢?其實它的作用遠比你想像中要來的大,這可不是單純可以做到先做基本運算這麼簡單的功能喔!他還可以做到零知識證明,怎麼做的?我們明天來一探究竟吧!


上一篇
Day 07 - 零知識證明EP05:交互式零知識證明缺點
下一篇
Day 09 - 零知識證明SP04:同態隱藏應用
系列文
淺談ZK Rollup30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

1
雷N
iT邦研究生 1 級 ‧ 2023-09-24 12:51:21

Homomorphism!!!
之前聽同事分享, 這部份的知識真的讓我對理解zk有幫助

確實,要認識現在檯面上的ZK,同態隱藏是不可或缺的知識。可以說現在實用的零知識技術,背後全部都是同態隱藏撐起來的。

我要留言

立即登入留言